package ds.hash;

public class MyHashII {

	private ObjectNode[] objectNodeArray;
	private int length;
	
	public MyHashII()
	{
		this(53); // 使用质数，在取mod的时候有利于分散聚集
	}
	
	public MyHashII(int length)
	{
		this.length = length;
		objectNodeArray = new ObjectNode[length];
	}
	
	public void insert(String key, Object value)
	{
		ObjectNode newNode = new ObjectNode(key, value);
		int hashValue = getHashValue(key);
		
		ObjectNode previousNode = null;
		ObjectNode currentNode = objectNodeArray[hashValue];
		while(currentNode!=null && !currentNode.getKey().equals(key))
		{
			previousNode = currentNode;
			currentNode = currentNode.getNext();
		}
		if(currentNode == objectNodeArray[hashValue])
			objectNodeArray[hashValue] = newNode;
		else
			previousNode.setNext(newNode);
	}
	
	public Object get(String key)
	{
		int hashValue = getHashValue(key);
		ObjectNode currentNode = objectNodeArray[hashValue];
		while(currentNode != null && !currentNode.getKey().equals(key))
		{
			currentNode = currentNode.getNext();
		}
		if(currentNode == null)
			return null;
		else
			return currentNode.getValue();
	}
	
	public Object delete(String key)
	{
		int hashValue = getHashValue(key);
		ObjectNode previousNode = null;
		ObjectNode currentNode = objectNodeArray[hashValue];
		while(currentNode != null && !currentNode.getKey().equals(key))
		{
			previousNode = currentNode;
			currentNode = currentNode.getNext();
		}
		
		// 没找到
		if(currentNode == null)
			return null;
		
		// 找到了，看看是否根节点，再对应操作
		if (currentNode == objectNodeArray[hashValue])
			objectNodeArray[hashValue] = null;
		else
			previousNode.setNext(currentNode.getNext());
		
		return currentNode.getValue();
			
	}
	
	/** 得到哈希值，自己定义的 */
	private int getHashValue(String key)
	{
		key = key.toLowerCase();
		int hashValue = 0;
		for(int i=0;i<key.length();i++)
		{
			int number = key.charAt(i) - 96;
			hashValue = (hashValue * 27 + number) % length;
		}
		return hashValue >=0? hashValue : -hashValue;
		
		/*
		int value = Math.abs(key.hashCode());
		return value % length;
		*/
	}
	
}

class ObjectNode
{
	private String key;
	private Object value;
	private ObjectNode next;
	
	public ObjectNode(String key, Object value)
	{
		this.key = key;
		this.value = value;
	}
	
	public String getKey() {
		return key;
	}
	public Object getValue() {
		return value;
	}

	public ObjectNode getNext() {
		return next;
	}

	public void setNext(ObjectNode next) {
		this.next = next;
	}	
	
}

class MyHashIIApp {
	public static void main(String[] args) {

		MyHashII mh2 = new MyHashII();
		Point p1 = new Point(1,2);
		Point p2 = new Point(3,4);
		Point p3 = new Point(5,6);
		Point p4 = new Point(7,8);
		Point p5 = new Point(9,10);
		Point p6 = new Point(9,10);
		Point p7 = new Point(9,10);
		mh2.insert("p1", p1);
		mh2.insert("p2", p2);
		mh2.insert("p3", p3);
		mh2.insert("p4", p4);
		mh2.insert("p5", p5);
		mh2.insert("p6", p6);
		mh2.insert("p7", p7);
		mh2.insert("p8", p7);
		
		System.out.println(mh2.get("p1"));
		System.out.println(mh2.get("p1").equals(p1));
		System.out.println(mh2.get("p2"));
		System.out.println(mh2.get("p2").equals(p2));
		System.out.println(mh2.get("p3"));
		System.out.println(mh2.get("p3").equals(p3));
		
	}
}